/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//反转链表+快慢指针找中间结点+双指针匹配
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow, *fast;
    slow = fast = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next;
        fast = fast->next;
    }
    return slow;
}

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL, *next = head;
    while(next){
        struct ListNode* obj = next->next;
        next->next = prev;
        prev = next;
        next = obj;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head) {
    struct ListNode* head1 = middleNode(head);
    struct ListNode* head2 = reverseList(head1);
    while(head2){
        if(head->val != head2->val){
            return false;
        }
        head = head->next;
        head2 = head2->next;
    }
    return true;
}

/*给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表。如果是，返回 true ；否则，返回 false 。*/